#include <iostream>
#include <cmath>
#include <random>
#include <ctime>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

// int k = 50;

long long Big_Rand(int multiple=10)
{
    long long sum = 0;
    for(int i=0;i<multiple;i++)
    {
        sum += rand();
    }
    return sum;
}

// double compute_once()
// {
//     int n = 2*k*k;
//     vector<vector<bool>> G;
//     vector<bool> tmp;
//     tmp.resize(n, false);
//     G.resize(n, tmp);
//     for(int i=0;i<=k-1;i++)
//     {
//         // 顶上那个request的边
//         for(int j=0;j<=k-1;j++)
//         {
//             G[i*(k+1)][i*2*k+j] = true;
//         }
//         // 第二层request的边
//         for(int j=1;j<=k;j++)
//         {
//             // G[i*(k+1)+j]是当前request
//             for(int z=j-1;z<=j-1+k-2;z++)
//             {
//                 G[i*(k+1)+j][i*2*k+(z%k)] = true;
//             }
//             G[i*(k+1)+j][i*2*k+k-1+j] = true;
//         }
//     }

//     // 第三层request的边
//     for(int i=0;i<=k-1;i++)
//     {
//         for(int j=0;j<=k-2;j++)
//         {
//             // 当前request G[k*k+k+ i*(k-1)+j]
//             for(int z=0;z<=k-1;z++)
//             {
//                 G[k*k+k+i*(k-1)+j][z*2*k+k+i] = true;
//             }
//         }
//     }


//     // TEST
//     // cout << "/**TEST**/" << endl;
//     // for(int i=0;i<G.size();i++)
//     // {
//     //     for(int j=0;j<G[i].size();j++)
//     //     {
//     //         cout << G[i][j] << " ";
//     //     }
//     //     cout << endl;
//     // }
//     // cout << "/**TEST**/" << endl;


//     vector<bool> matched;
//     matched.resize(n, false);
//     vector<double> rank(n);
//     for(int i=0;i<n;i++)
//     {
//         rank[i] = (1.0 * Big_Rand()) / (10.0 * RAND_MAX);
//     }
//     for(int i=0;i<n;i++)
//     {
//         vector<int> unmatched_neighbor;
//         for(int j=0;j<n;j++)
//         {
//             if(G[i][j] && !matched[j])
//             {
//                 unmatched_neighbor.push_back(j);
//             }
//         }
//         if(unmatched_neighbor.size() == 0)
//         {
//             // NO availble neighbor
//             // DO NOTHING
//         }
//         else
//         {
//             int min_index = -1;
//             double min_value = 2;
//             for(int z=0;z<unmatched_neighbor.size();z++)
//             {
//                 if(rank[unmatched_neighbor[z]] < min_value)
//                 {
//                     min_value = rank[unmatched_neighbor[z]];
//                     min_index = unmatched_neighbor[z];
//                 }
//             }
//             matched[min_index] = true;
//         }
//     }
//     int res = 0;
//     for(int i=0;i<n;i++)
//     {
//         if(matched[i])
//         {
//             res++;
//         }
//     }
//     return double(res) / double(n);
// }

// int main()
// {
//     int loop = 1000;
//     double res = 0;
//     clock_t start_time = clock();
//     for(int i=0;i<loop;i++)
//     {
//         res += compute_once();
//         if((i+1)%100 == 0)
//         {
//             cout << i+1 << "-loop, the ratio is " << res / double(i+1) << endl;
//         }
//     }
//     clock_t end_time = clock();
//     cout << "The run time is: " <<(double)(end_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
//     return 0;
// }

vector<bool> compute_once(int k)
{
    int n = 2*k;
    // cout << n << endl;
    vector<vector<bool>> G;
    vector<bool> tmp;
    tmp.resize(n, false);
    G.resize(k+1, tmp);
    for(int i=0;i<=0;i++)
    {
        // 顶上那个request的边
        for(int j=0;j<=k-1;j++)
        {
            G[i*(k+1)][i*2*k+j] = true;
        }
        // 第二层request的边
        for(int j=1;j<=k;j++)
        {
            // G[i*(k+1)+j]是当前request
            for(int z=j-1;z<=j-1+k-2;z++)
            {
                G[i*(k+1)+j][i*2*k+(z%k)] = true;
            }
            G[i*(k+1)+j][i*2*k+k-1+j] = true;
        }
    }

    // 第三层request的边
    // for(int i=0;i<=k-1;i++)
    // {
    //     for(int j=0;j<=k-2;j++)
    //     {
    //         // 当前request G[k*k+k+ i*(k-1)+j]
    //         for(int z=0;z<=k-1;z++)
    //         {
    //             G[k*k+k+i*(k-1)+j][z*2*k+k+i] = true;
    //         }
    //     }
    // }


    // TEST
    // cout << "/**TEST**/" << endl;
    // for(int i=0;i<G.size();i++)
    // {
    //     for(int j=0;j<G[i].size();j++)
    //     {
    //         cout << G[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << "/**TEST**/" << endl;


    vector<bool> matched;
    matched.resize(n, false);
    vector<double> rank(n);
    for(int i=0;i<n;i++)
    {
        rank[i] = (1.0 * Big_Rand()) / (10.0 * RAND_MAX);
    }
    for(int i=0;i<k+1;i++)
    {
        vector<int> unmatched_neighbor;
        for(int j=0;j<n;j++)
        {
            if(G[i][j] && !matched[j])
            {
                unmatched_neighbor.push_back(j);
            }
        }
        if(unmatched_neighbor.size() == 0)
        {
            // NO availble neighbor
            // DO NOTHING
        }
        else
        {
            int min_index = -1;
            double min_value = 2;
            for(int z=0;z<unmatched_neighbor.size();z++)
            {
                if(rank[unmatched_neighbor[z]] < min_value)
                {
                    min_value = rank[unmatched_neighbor[z]];
                    min_index = unmatched_neighbor[z];
                }
            }
            matched[min_index] = true;
        }
    }
    vector<bool> MATCHED(k);
    for(int i=0;i<k;i++)
    {
        MATCHED[i] = matched[k+i];
    }
    return MATCHED;
}

double result(vector<long long int> P, int loop, int k)
{
    double sum = 0.0;
    for(int i=0;i<k;i++)
    {
        double real_pi = P[i] * 1.0 / (loop * 1.0);
        real_pi = 1.0 - real_pi;
        sum += 1.0 * (k* real_pi - 1.0 * pow(real_pi, k));
    }
    // for(int i=0;i<k;i++)
    // {
    //     cout << P[i] * 1.0 / (1.0 * loop) << " ";
    // }
    // cout << endl;
    return  (sum + 1.0 * k * (k+1.0)) / (2.0 * k * k);
}

int main()
{
    int loop = 10000000;
    // double res = 0;
    clock_t start_time = clock();
    std::fstream file1, file2;
    file1.open("result.txt", ios::out);
    file2.open("log.txt", ios::out);
    
    for(int k=39;k<=50;k++)
    {
        double final_res = 0.0;
        vector<long long int> P;
        P.resize(k, 0);
        for(int i=0;i<loop;i++)
        {
            vector<bool> tmp = compute_once(k);
            for(int j=0;j<k;j++)
            {
                if(tmp[j])
                {
                    P[j] += 1;
                }
            }
            if((i+1)%1000000 == 0)
            {
                double res = result(P, i+1, k);
                final_res = res;
                file2 << "when k = " << k << ", "<< i+1 << "-th loop, the avg ratio is " << res << endl;
            }
        }
        clock_t end_time = clock();
        file1 << "The run time is: " <<(double)(end_time - start_time) / CLOCKS_PER_SEC << "s" << ", the result is " << final_res << endl;
    }
    file1.close();
    file2.close();
    return 0;
}